﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
// 原题连接：https://leetcode.cn/problems/remove-linked-list-elements/
/*
题目描述：
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：
输入：head = [], val = 1
输出：[]

示例 3：
输入：head = [7,7,7,7], val = 7
输出：[]
 

提示：
列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50
*/


 // Definition for singly-linked list.
  struct ListNode {
      int val;
      struct ListNode *next;
  };
 

// 方法1——直接遍历

struct ListNode* removeElements(struct ListNode* head, int val) {
    if (NULL == head) {
        return NULL;
    }
    struct ListNode* cur = head;
    struct ListNode* pre = NULL;
    while (cur) {
        if (val == cur->val) {
            if (cur == head) { // 头删
                head = cur->next;
                free(cur);
                cur = head;
            }
            else {
                pre->next = cur->next;
                free(cur);
                cur = pre->next;
            }
        }
        else { // 迭代地往后走
            pre = cur;
            cur = cur->next;
        }
    }
    return head;
}
// 时间复杂度O(n)，n为链表的长度。
// 空间复杂度：O(1)，我们只需要用到常数级的额外空间。